package test230608;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/7 23:55
 * 1027. 最长等差数列
 * https://leetcode.cn/problems/longest-arithmetic-subsequence/
 */
@SuppressWarnings({"all"})
public class Solution01 {

    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();  // 用于将数据存到 map 中, 便于查找
        int[][] dp = new int[n][n];  // 表示 i j 位置结尾的等差数列子序列的最大长度
        // 状态初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        // 动态规划过程
        int maxLen = 2;  // 记录最大长度
        map.put(nums[0], 0);  // 先将 0 位置的存储到哈希表中
        for (int i = 1; i < n; i++) {  // 先固定倒数第 2 个数字, 即 i 位置, 使边遍历边存储 map 时的可能存在的 a 与 i 最近
            for (int j = i + 1; j < n; j++) {
                int a = 2 * nums[i] - nums[j];
                if (map.containsKey(a)) {
                    dp[i][j] = dp[map.get(a)][i] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
            map.put(nums[i], i);
        }
        return maxLen;
    }
}
